Easy2Siksha.com
GNDU QUESTION PAPERS 2021
BA/BSc 4
th
SEMESTER
COMPUTER SCIENCE
(Data Structures & Programming Language Using C++)
Time Allowed: 3 Hours Maximum Marks: 75
Note: Aempt Five quesons in all, selecng at least One queson from each secon. The
Fih queson may be aempted from any secon. All quesons carry equal marks.
1. What is an array and its types? How muldimensional arrays are stored in memory?
Explain row major representaon of an array. Write a program to add and remove an
element from an array.
2. (A) What is me complexity of an algorithm? Explain with example.
(B) What are the dierent types of data structure available and what are the points to be
considered before choosing a data structure?
3. Explain Stack. What is meant by posix expressions? How posix expressions are
evaluated by using stacks ?
4. Dene queue. Explain the linked representaon of queue and operaons to be
performed on it with the help of suitable example.
5. What is Bubble Sort ? Consider the following numbers are stored in an array A: 37, 52,
28, 75, 61, 24, 9, 59. Apply Bubble sort algorithm to the array A and show each pass
separately.
6. Write the algorithm to sort a list using Quick Sort and discuss the complexity.
Easy2Siksha.com
7. (A) What is an Object? How Objects can be dened and accessed in C ++?
(B) What is dierence between public and private member funcons?
(C) Explain the need of inheritance with help of an example.
8. What is operator overloading? What is the need of overloading an operator? I ist the
operators that can be overloaded and one that cannot be overloaded. Give reasons why
some operators cannot be overloaded.
Easy2Siksha.com
GNDU ANSWER PAPERS 2021
BA/BSc 4
th
SEMESTER
COMPUTER SCIENCE
(Data Structures & Programming Language Using C++)
Time Allowed: 3 Hours Maximum Marks: 75
Note: Aempt Five quesons in all, selecng at least One queson from each secon. The
Fih queson may be aempted from any secon. All quesons carry equal marks.
1. What is an array and its types? How muldimensional arrays are stored in memory?
Explain row major representaon of an array. Write a program to add and remove an
element from an array.
Ans: 1. What is an Array?
Imagine you are storing the names of your friends. You could create 10 separate variables—
name1, name2, name3, and so on. But this becomes messy, confusing, and difficult to
manage.
A better way is to store all similar items together in one structure.
That structure is called an array.
Definition
An array is a collection of elements of the same data type stored at contiguous (side-by-
side) memory locations.
This means if the first element is at address 1000, the next elements will be stored at 1002,
1004, 1006… (in case of 2-byte integers).
Why do we use arrays?
• They allow quick access to data.
• They store values in a structured way.
• They make operations like searching, sorting, or updating very efficient.
• They are easy to declare and use.
Easy2Siksha.com
You can think of an array as a row of houses where each house has a number (index) and
each house stores one value.
2. Types of Arrays
Arrays can be of two main types:
A. One-Dimensional Array (1D Array)
A 1D array is like a single row of elements.
Example:
int marks[5];
This creates 5 boxes: marks[0], marks[1], … marks[4].
You can picture it as:
Index
0
1
2
3
4
Value
50
60
72
85
90
It is the simplest type of array.
B. Multidimensional Array (2D, 3D, etc.)
A 2D array is like a table consisting of rows and columns.
Example:
int a[3][4];
This means the array has 3 rows and 4 columns, like a matrix.
Visual representation:
C0
C1
C2
C3
R0
R1
R2
You can also have 3D arrays (like a cube), but they are rarely used by beginners.
3. How Multidimensional Arrays Are Stored in Memory
Even though a 2D array looks like a grid, memory is always linear, meaning it is a single
continuous line.
Easy2Siksha.com
So how does the computer store this table-like structure in a single line of memory?
It stores it row by row or column by column, depending on the language.
There are two methods:
A. Row-Major Order (used by C, C++, Java, Python)
All elements of the first row are stored first, then all elements of the second row, and so on.
For example, for array
a[3][3]
1 2 3
4 5 6
7 8 9
Row-major storage will be:
1 2 3 4 5 6 7 8 9
B. Column-Major Order (used by Fortran, MATLAB)
Here, columns are stored first.
So the same matrix becomes:
1 4 7 2 5 8 3 6 9
4. Row-Major Representation of a 2D Array (Formula)
In row-major order:
Address of element A[i][j] is:
LOC(A[i][j]) = BaseAddress + [ (i × NumberOfColumns) + j ] × SizeOfEachElement
Where:
• i = row index
• j = column index
• NumberOfColumns = total columns in the array
• SizeOfEachElement = size of data type (e.g., 4 bytes for int)
Easy2Siksha.com
Example
Let array be A[3][3], integers (4 bytes each).
Base Address = 1000
Find address of A[1][2].
Apply formula:
LOC = 1000 + [ (1 × 3) + 2 ] × 4
= 1000 + (3 + 2) × 4
= 1000 + 5 × 4
= 1000 + 20
= 1020
So A[1][2] will be stored at address 1020.
5. Program to Add and Remove an Element from an Array
Below are very simple programs in C language.
(You can easily convert to Java or Python.)
Program to Insert/Add an Element in an Array
Logic
1. Shift elements from right to create space at the desired position.
2. Insert the new element.
3. Increase the size of the array.
C Program
#include <stdio.h>
int main() {
int arr[100], n, pos, value;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements: ");
for(int i=0; i<n; i++)
scanf("%d", &arr[i]);
Easy2Siksha.com
printf("Enter position to insert (0 to %d): ", n);
scanf("%d", &pos);
printf("Enter value to insert: ");
scanf("%d", &value);
// Shift elements to right
for(int i=n; i>pos; i--) {
arr[i] = arr[i-1];
}
arr[pos] = value;
n++;
printf("Array after insertion: ");
for(int i=0; i<n; i++)
printf("%d ", arr[i]);
return 0;
}
Program to Delete/Remove an Element from an Array
Logic
1. Shift elements to the left starting from the deletion position.
2. Reduce array size by 1.
C Program
#include <stdio.h>
int main() {
int arr[100], n, pos;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements: ");
for(int i=0; i<n; i++)
scanf("%d", &arr[i]);
printf("Enter position to delete (0 to %d): ", n-1);
scanf("%d", &pos);
// Shift left
Easy2Siksha.com
for(int i=pos; i<n-1; i++) {
arr[i] = arr[i+1];
}
n--;
printf("Array after deletion: ");
for(int i=0; i<n; i++)
printf("%d ", arr[i]);
return 0;
}
Conclusion
Arrays are one of the most important and fundamental data structures in programming.
They make it easy to store and manage large amounts of data in a clean, organized, and
efficient way. You learned:
• What an array is
• Types of arrays (1D and multidimensional)
• How multidimensional arrays are stored in linear memory
• Row-major representation with formula
• Programs to insert and delete elements
This understanding builds the foundation for many other advanced data structures like
matrices, graphs, linked lists, stacks, queues, and more.
2. (A) What is me complexity of an algorithm? Explain with example.
(B) What are the dierent types of data structure available and what are the points to be
considered before choosing a data structure?
Ans: Introduction
When we study computer science, two ideas keep appearing again and again: algorithms
and data structures. Algorithms are step-by-step instructions to solve a problem, while data
structures are ways of organizing information so that algorithms can work efficiently.
But here’s the catch: not all algorithms are equally fast, and not all data structures are
equally suitable. To judge them, we use concepts like time complexity and carefully choose
data structures based on the problem. Let’s break this down in a simple, engaging way.
Easy2Siksha.com
Part A: Time Complexity of an Algorithm
1. What is Time Complexity?
Time complexity is a way to measure how much time an algorithm takes to run, depending
on the size of the input.
• Imagine you are searching for a book in a library.
• If the library has 100 books, it might take you 10 minutes.
• If the library has 10,000 books, it will take much longer.
Time complexity tells us how the running time grows as the input size grows.
2. Big-O Notation
We usually express time complexity using Big-O notation. Big-O gives us the worst-case
scenario of how fast or slow an algorithm can be.
Some common complexities:
• O(1): Constant time → The algorithm takes the same time no matter the input size.
• O(log n): Logarithmic time → Time grows slowly even if input grows large.
• O(n): Linear time → Time grows directly with input size.
• O(n²): Quadratic time → Time grows very fast as input increases.
3. Example: Linear Search vs Binary Search
Linear Search
• Suppose you have a list of numbers and you want to find one number.
• You check each number one by one until you find it.
• If there are n numbers, in the worst case you check all of them.
• Time complexity: O(n).
If there are 1,000 numbers, you may need 1,000 checks.
Binary Search
• Now imagine the list is sorted.
• You check the middle number: if it’s too big, you search the left half; if it’s too small,
you search the right half.
• Each step cuts the list in half.
• Time complexity: O(log n).
If there are 1,000 numbers, you only need about 10 checks.
Comparison:
Easy2Siksha.com
• Linear search is simple but slow for large inputs.
• Binary search is faster but requires sorted data.
This shows why time complexity matters—it helps us choose the right algorithm for the job.
Part B: Data Structures
1. What are Data Structures?
Data structures are ways of organizing and storing data so that algorithms can use them
efficiently.
Think of data structures like containers:
• A stack is like a pile of plates—last in, first out.
• A queue is like a line at a ticket counter—first in, first out.
• A tree is like a family chart—branches connecting parents and children.
2. Types of Data Structures
(i) Primitive Data Structures
• Basic building blocks: integers, floats, characters, booleans.
• Example: storing age as an integer.
(ii) Non-Primitive Data Structures
These are more complex and divided into two categories:
a) Linear Data Structures
• Data is arranged in a sequence.
• Examples:
o Arrays: Fixed-size collection of elements.
o Linked Lists: Elements connected by pointers.
o Stacks: Last In, First Out (LIFO).
o Queues: First In, First Out (FIFO).
b) Non-Linear Data Structures
• Data is arranged hierarchically or in networks.
• Examples:
o Trees: Hierarchical structure (e.g., binary tree).
o Graphs: Nodes connected by edges, useful for networks.
3. Points to Consider Before Choosing a Data Structure
Easy2Siksha.com
Choosing the right data structure is like choosing the right tool for a job. Here are the key
points:
(i) Nature of the Data
• Is the data numeric, textual, or relational?
• Example: For hierarchical data like family trees, use a tree structure.
(ii) Operations Needed
• Do you need fast searching, inserting, or deleting?
• Example:
o For fast searching, use hash tables.
o For frequent insertions/deletions, use linked lists.
(iii) Memory Usage
• Some data structures use more memory.
• Example: Arrays are memory-efficient but fixed in size; linked lists use extra memory
for pointers.
(iv) Time Complexity of Operations
• Consider how quickly operations can be performed.
• Example: Searching in an array is O(n), but in a balanced binary search tree it’s O(log
n).
(v) Flexibility and Scalability
• Will the data grow?
• Example: If the size is unpredictable, avoid arrays and use dynamic structures like
linked lists.
(vi) Ease of Implementation
• Sometimes a simpler data structure is better, even if it’s less efficient.
• Example: Arrays are easier to implement than trees.
Conclusion
Time complexity helps us judge the efficiency of algorithms, while data structures provide
the foundation for storing and managing data. Together, they form the backbone of
computer science.
An efficient algorithm with the wrong data structure is like a fast car on a broken road—it
won’t perform well. Similarly, the right data structure with a poor algorithm won’t solve
problems quickly.
Easy2Siksha.com
By understanding time complexity and carefully choosing data structures, we can design
systems that are not only correct but also fast, efficient, and scalable.
3. Explain Stack. What is meant by posix expressions? How posix expressions are
evaluated by using stacks ?
Ans: 1. What is a Stack?
Imagine you have a stack of plates in your kitchen. When you add new plates, you always
place them on the top of the pile. If you want a plate to use, you cannot pull a plate from
the bottom or the middle; you always take the plate from the top.
This is exactly how a stack works in computer science.
A stack is a linear data structure that follows a very strict rule called:
LIFO — Last In, First Out
This means:
• The last item that you put into the stack will be the first item to come out.
• You cannot directly access the middle or bottom element.
• You can only work with the top element.
Real-Life Examples of Stack
• A stack of books.
• Undo operation in MS Word (last action undone first).
• Browser history (you go back step by step in reverse order).
Operations on a Stack
A stack mainly supports two operations:
1. PUSH → Add an element to the top
2. POP → Remove an element from the top
Other helpful operations:
• PEEK/TOP → View the top element without removing it
• IS EMPTY → Check if stack has no element
• IS FULL → Check if stack is completely filled (in case of a fixed-size stack)
Easy2Siksha.com
So, a stack is simply a controlled way of storing and removing data—just like handling a pile
of plates.
2. What is a Postfix Expression? (Made Easy)
We normally write mathematical expressions like this:
A + B
3 * (4 + 2)
(6 - 2) / 4
This format is called Infix notation, where the operator (+, -, *, /) comes between the
operands.
But infix has one big problem:
• The computer gets confused because it must check brackets, operator precedence,
and associativity.
To make calculation easier for computers, two alternate notations are used:
1. Prefix (Polish notation)
2. Postfix (Reverse Polish notation)
So what is Postfix notation?
In postfix notation, the operator comes after the operands.
Examples:
• Infix: A + B
Postfix: AB+
• Infix: (3 + 4) * 5
Postfix: 34+5*
• Infix: (6 - 2) / (1 + 1)
Postfix: 62-11+/
There are NO brackets in postfix expressions because their order is unambiguous.
Why postfix is useful?
• Computers can evaluate postfix expressions very easily using a stack.
• No need to remember priority rules (like * comes before +).
• No need for brackets.
• Easy to convert algorithms from infix to postfix.
Easy2Siksha.com
Thus, postfix is simple, efficient, and ideal for computer processing.
3. How Postfix Expressions Are Evaluated Using Stack? (Step-by-Step)
This is the heart of the topic.
Evaluating postfix expressions using a stack is like following a simple recipe.
We read the expression from left to right, and we use a stack to store values temporarily.
Basic Rule
• If the symbol is an operand, PUSH it into the stack.
• If the symbol is an operator, POP two elements from the stack:
o The first popped element → right operand
o The second popped element → left operand
o Perform the operation
o PUSH the result back into the stack
At the end, only one element remains in the stack, and that is the final answer.
4. Example of Postfix Evaluation (Very Easy Explanation)
Let’s take a simple postfix expression:
23+5*
This means: (2 + 3) * 5
Let’s evaluate using stack.
Step-by-Step Table
Symbol
Action
Stack
2
Operand → PUSH
2
3
Operand → PUSH
2, 3
+
Operator → POP 3 and 2 → Compute 2+3=5 → PUSH 5
5
5
Operand → PUSH
5, 5
*
Operator → POP 5 and 5 → Compute 5*5=25 → PUSH 25
25
Now the stack has only one value: 25
This is the final result.
5. Another Example (Slightly Bigger)
Easy2Siksha.com
Postfix:
462/+3*
Let’s evaluate:
1. Read 4 → push
2. Read 6 → push
3. Read 2 → push
4. Read / → pop 2 and 6 → 6/2 = 3 → push 3
Stack: 4, 3
5. Read + → pop 3 and 4 → 4+3 = 7 → push 7
Stack: 7
6. Read 3 → push
Stack: 7, 3
7. Read * → pop 3 and 7 → 7 * 3 = 21 → push 21
Final answer = 21
6. Why Stack Is the Perfect Tool for Postfix Evaluation?
Postfix evaluation requires us to temporarily save numbers until an operator appears.
A stack fits perfectly because:
• The latest number we saw is the first one needed for any operator.
• We always pop numbers in reverse order (right operand first), which matches postfix
logic.
• The stack grows and shrinks automatically according to the expression.
Thus, stack + postfix = best combination.
4. Dene queue. Explain the linked representaon of queue and operaons to be
performed on it with the help of suitable example.
Ans: Introduction
In computer science, data structures are like different ways of organizing books in a library.
Some shelves let you pick any book directly (like arrays), while others make you follow a
strict order. A queue is one such structure where order matters—it works on the principle
of First In, First Out (FIFO).
Easy2Siksha.com
Imagine standing in line at a ticket counter. The person who comes first gets served first,
and the person who comes last has to wait. That’s exactly how a queue works in
programming.
Now let’s explore what a queue is, how it can be represented using linked lists, and the
operations we can perform on it—all explained in a simple, engaging way.
Definition of Queue
A queue is a linear data structure that follows the FIFO principle:
• First In → First Out
• The element inserted first is the one removed first.
Real-life analogy:
• A queue at a bus stop.
• The first passenger in line boards the bus first.
• The last passenger boards last.
Representation of Queue
Queues can be represented in two main ways:
1. Array Representation – Using a fixed-size array.
2. Linked Representation – Using nodes connected by pointers.
Here, we focus on the linked representation, which is more flexible because it doesn’t
require a fixed size.
Linked Representation of Queue
In a linked queue:
• Each element is stored in a node.
• A node has two parts:
o Data (the actual value)
o Next pointer (address of the next node)
• Two special pointers are maintained:
o Front → Points to the first node (element to be removed next).
o Rear → Points to the last node (element most recently added).
Think of it like a chain of people holding hands:
• The front person is the one who will leave first.
• The rear person is the one who just joined the line.
Easy2Siksha.com
Operations on Queue
Queues support several basic operations. Let’s go through them one by one with examples.
1. Enqueue (Insertion)
• Adds an element at the rear of the queue.
• Steps:
1. Create a new node with the given data.
2. If the queue is empty, both front and rear point to this node.
3. Otherwise, link the new node at the end and update rear.
Example:
• Queue: [10 → 20 → 30]
• Enqueue 40 → [10 → 20 → 30 → 40]
• Rear now points to 40.
2. Dequeue (Deletion)
• Removes an element from the front of the queue.
• Steps:
1. Check if the queue is empty. If yes, report underflow.
2. Otherwise, remove the node at front.
3. Update front to point to the next node.
Example:
• Queue: [10 → 20 → 30 → 40]
• Dequeue → Removes 10 → [20 → 30 → 40]
• Front now points to 20.
3. Peek (Front Element)
• Returns the element at the front without removing it.
• Useful when you just want to see who is next in line.
Example:
• Queue: [20 → 30 → 40]
• Peek → Returns 20.
4. IsEmpty (Check if Queue is Empty)
• Returns true if front = NULL.
• Example: If queue has no elements, IsEmpty → True.
Easy2Siksha.com
5. IsFull (Check if Queue is Full)
• In linked representation, the queue is never “full” unless memory runs out.
• So practically, IsFull is not needed here.
🖼 Example in C-like Pseudocode
struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node* front;
struct Node* rear;
};
// Enqueue operation
void enqueue(struct Queue* q, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = newNode;
return;
}
q->rear->next = newNode;
q->rear = newNode;
}
// Dequeue operation
int dequeue(struct Queue* q) {
if (q->front == NULL) {
printf("Queue Underflow");
return -1;
}
struct Node* temp = q->front;
int value = temp->data;
q->front = q->front->next;
if (q->front == NULL) q->rear = NULL;
free(temp);
return value;
}
This code shows how enqueue and dequeue work using linked nodes.
Easy2Siksha.com
Conclusion
Queues are one of the simplest yet most powerful data structures. Their linked
representation makes them flexible, allowing dynamic growth without worrying about fixed
sizes. By mastering operations like enqueue and dequeue, we can handle real-world
problems like scheduling tasks, managing printers, or simulating waiting lines.
In essence, queues teach us the importance of order and fairness—just like in life, those
who come first should be served first.
5. What is Bubble Sort ? Consider the following numbers are stored in an array A: 37, 52,
28, 75, 61, 24, 9, 59. Apply Bubble sort algorithm to the array A and show each pass
separately.
Ans: What is Bubble Sort?
Imagine you have a row of students standing randomly based on height, but you want them
to stand in ascending order—from the shortest to the tallest. Instead of asking everyone to
rearrange themselves at once, you tell them to check one pair at a time:
• Compare Student 1 with Student 2.
• If Student 1 is taller, swap them.
• Then compare Student 2 with Student 3, and swap if needed.
• Continue till the end.
At the end of this first round, the tallest student naturally moves to the last position—just
like a bubble floating to the top of water.
That’s why we call it Bubble Sort.
Bubble Sort works by repeatedly comparing adjacent elements (side-by-side), and swapping
them if they are in the wrong order. After each full pass, the largest remaining number
"bubbles up" to its correct position.
Given Data
You are asked to apply Bubble Sort on the following array:
A = [37, 52, 28, 75, 61, 24, 9, 59]
We will sort it in ascending order.
Now let’s walk through the passes one by one.
Easy2Siksha.com
Let’s Perform Bubble Sort (Step-by-Step Passes)
PASS 1
We compare adjacent elements:
Comparison
Action
Array After Step
37 & 52
37 < 52 → no swap
37, 52, 28, 75, 61, 24, 9, 59
52 & 28
swap
37, 28, 52, 75, 61, 24, 9, 59
52 & 75
no swap
37, 28, 52, 75, 61, 24, 9, 59
75 & 61
swap
37, 28, 52, 61, 75, 24, 9, 59
75 & 24
swap
37, 28, 52, 61, 24, 75, 9, 59
75 & 9
swap
37, 28, 52, 61, 24, 9, 75, 59
75 & 59
swap
37, 28, 52, 61, 24, 9, 59, 75
End of Pass 1:
[37, 28, 52, 61, 24, 9, 59, 75]
Largest element 75 is now in its correct place.
PASS 2
Comparison
Action
Result
37 & 28
swap
28, 37, 52, 61, 24, 9, 59, 75
37 & 52
no swap
28, 37, 52, 61, 24, 9, 59, 75
52 & 61
no swap
28, 37, 52, 61, 24, 9, 59, 75
61 & 24
swap
28, 37, 52, 24, 61, 9, 59, 75
61 & 9
swap
28, 37, 52, 24, 9, 61, 59, 75
61 & 59
swap
28, 37, 52, 24, 9, 59, 61, 75
End of Pass 2:
[28, 37, 52, 24, 9, 59, 61, 75]
Second-largest number 61 reaches its place.
PASS 3
Comparison
Action
Result
28 & 37
no swap
28, 37, 52, 24, 9, 59, 61, 75
37 & 52
no swap
28, 37, 52, 24, 9, 59, 61, 75
52 & 24
swap
28, 37, 24, 52, 9, 59, 61, 75
Easy2Siksha.com
52 & 9
swap
28, 37, 24, 9, 52, 59, 61, 75
52 & 59
no swap
28, 37, 24, 9, 52, 59, 61, 75
End of Pass 3:
[28, 37, 24, 9, 52, 59, 61, 75]
PASS 4
Comparison
Action
Result
28 & 37
no swap
28, 37, 24, 9, 52, 59, 61, 75
37 & 24
swap
28, 24, 37, 9, 52, 59, 61, 75
37 & 9
swap
28, 24, 9, 37, 52, 59, 61, 75
37 & 52
no swap
28, 24, 9, 37, 52, 59, 61, 75
End of Pass 4:
[28, 24, 9, 37, 52, 59, 61, 75]
PASS 5
Comparison
Action
Result
28 & 24
swap
24, 28, 9, 37, 52, 59, 61, 75
28 & 9
swap
24, 9, 28, 37, 52, 59, 61, 75
28 & 37
no swap
24, 9, 28, 37, 52, 59, 61, 75
End of Pass 5:
[24, 9, 28, 37, 52, 59, 61, 75]
PASS 6
Comparison
Action
Result
24 & 9
swap
9, 24, 28, 37, 52, 59, 61, 75
24 & 28
no swap
9, 24, 28, 37, 52, 59, 61, 75
End of Pass 6:
[9, 24, 28, 37, 52, 59, 61, 75]
PASS 7
Comparison
Action
Result
Easy2Siksha.com
9 & 24
no swap
9, 24, 28, 37, 52, 59, 61, 75
End of Pass 7:
Array is now fully sorted.
Final Sorted Array
[9, 24, 28, 37, 52, 59, 61, 75]
Conclusion
Bubble Sort is a simple algorithm that teaches you the foundations of comparison-based
sorting. It works by repeatedly comparing and swapping adjacent values. With each pass,
the largest unsorted value "bubbles up" to its correct position, just like a bubble rising to the
surface of water.
By walking through each pass, you can clearly see how the messy unsorted list slowly
transforms into an ordered, neat sequence.
6. Write the algorithm to sort a list using Quick Sort and discuss the complexity.
Ans: Introduction
Sorting is one of the most common tasks in computer science. Whether you’re arranging
names alphabetically, organizing numbers in ascending order, or managing records in a
database, sorting makes data easier to use. Among the many sorting techniques, Quick Sort
stands out as one of the fastest and most efficient.
Quick Sort was developed by Tony Hoare in 1960, and even today it remains a favorite
because of its speed and elegance. It uses a clever strategy called divide and conquer—
breaking a big problem into smaller ones, solving them, and then combining the results.
Let’s explore the algorithm step by step, understand how it works with examples, and then
discuss its complexity in detail.
The Idea Behind Quick Sort
Quick Sort works by choosing a special element called the pivot.
• All elements smaller than the pivot are moved to its left.
Easy2Siksha.com
• All elements greater than the pivot are moved to its right.
• The pivot is now in its correct position.
• The same process is repeated for the left and right parts until the whole list is sorted.
Think of it like organizing books: pick one book as a reference (pivot), put all lighter
books on one side and heavier books on the other. Repeat the process for each side until
the shelf is perfectly arranged.
Algorithm for Quick Sort
Here’s the step-by-step algorithm in simple terms:
Algorithm: Quick Sort
1. Start with a list of elements.
2. Choose a pivot element.
o This can be the first element, last element, middle element, or chosen
randomly.
3. Partition the list.
o Rearrange the list so that:
▪ Elements smaller than pivot are on the left.
▪ Elements greater than pivot are on the right.
4. Place the pivot in its correct position.
5. Recursively apply Quick Sort to the left and right sublists.
6. Stop when sublists have one or zero elements (already sorted).
Example Walkthrough
Suppose we want to sort the list:
[35, 12, 43, 8, 51]
1. Choose pivot = 35.
2. Partition:
o Left side: [12, 8]
o Pivot: [35]
o Right side: [43, 51] → Result: [12, 8] [35] [43, 51]
3. Apply Quick Sort to [12, 8]:
o Pivot = 12
o Left: [8], Pivot: [12], Right: [] → Sorted: [8, 12]
4. Apply Quick Sort to [43, 51]:
o Pivot = 43
o Left: [], Pivot: [43], Right: [51] → Sorted: [43, 51]
5. Combine everything:
[8, 12, 35, 43, 51]
Easy2Siksha.com
The list is now sorted!
Pseudocode for Quick Sort
QuickSort(arr, low, high):
if low < high:
pivotIndex = Partition(arr, low, high)
QuickSort(arr, low, pivotIndex - 1)
QuickSort(arr, pivotIndex + 1, high)
Partition(arr, low, high):
pivot = arr[high] // choose last element as pivot
i = low - 1
for j = low to high - 1:
if arr[j] <= pivot:
i = i + 1
swap arr[i] and arr[j]
swap arr[i + 1] and arr[high]
return (i + 1)
Complexity of Quick Sort
Now let’s discuss how efficient Quick Sort is.
1. Best Case
• Pivot divides the list into two equal halves each time.
• Time complexity: O(n log n)
• Example: Sorting [10, 20, 30, 40, 50] with pivot chosen wisely.
2. Average Case
• Pivot divides the list reasonably well (not perfectly balanced, but not too skewed).
• Time complexity: O(n log n)
• This is the most common scenario.
3. Worst Case
• Pivot is always the smallest or largest element.
• The list is divided into one big part and one tiny part.
• Time complexity: O(n²)
• Example: Sorting [10, 20, 30, 40, 50] if pivot is always chosen as the smallest
element.
To avoid worst case, we often choose pivot randomly or use the “median-of-three”
method (pick median of first, middle, and last elements).
Easy2Siksha.com
4. Space Complexity
• Quick Sort is an in-place algorithm (doesn’t need extra arrays).
• Space complexity: O(log n) due to recursive calls.
Conclusion
Quick Sort is like a master organizer—it breaks problems into smaller parts and solves them
efficiently. While its worst case can be slow, in practice it is one of the fastest sorting
algorithms, especially for large datasets. Its elegance lies in simplicity: pick a pivot, divide,
and conquer.
That’s why Quick Sort remains a favorite in computer science classrooms and real-world
applications alike.
7. (A) What is an Object? How Objects can be dened and accessed in C ++?
(B) What is dierence between public and private member funcons?
(C) Explain the need of inheritance with help of an example.
Ans: Introduction
C++ is a powerful programming language that supports Object-Oriented Programming
(OOP).
OOP tries to model real-world things into code. Just like we look around and see objects—
cars, mobiles, animals, books—C++ also creates objects to represent things in a program.
These objects can store data and perform actions. To manage these objects, C++ uses
important concepts like classes, access specifiers (public/private), and inheritance.
In this answer, we will understand three important parts of OOP:
1. What an object is and how to create and use it in C++.
2. How public and private members differ.
3. Why inheritance is needed, with a clear example.
(A) What Is an Object? How Objects Are Defined and Accessed in C++?
➤ What is an Object?
An object in C++ is something that has two things:
1. Data (attributes) → for example, a car has color, speed, and model number.
2. Functions (behaviour) → like starting the engine, stopping, or accelerating.
Easy2Siksha.com
Objects are created from classes, just like toys are created using a mould.
• Class → blueprint
• Object → actual usable item made from the blueprint
Example from real life:
Think of a "Mobile Phone" class. Every mobile has:
• Data: brand, price, RAM
• Functions: call(), message(), clickPhoto()
Each mobile phone you actually use is an object.
➤ How to Define an Object in C++
First, we create a class.
Then we create objects of that class.
Syntax:
class ClassName {
// data members
// member functions
};
int main() {
ClassName objectName; // object creation
}
Example:
class Car {
public:
string model;
int speed;
void show() {
cout << "Model: " << model << ", Speed: " << speed;
}
};
int main() {
Car c1; // defining object
c1.model = "Honda City";
c1.speed = 180;
c1.show(); // accessing object’s function
}
Easy2Siksha.com
➤ How Objects Are Accessed?
Objects in C++ are accessed using the dot (.) operator.
objectName.dataMember
objectName.functionName()
Example:
c1.speed = 150; // accessing data
c1.show(); // calling function
This is how C++ allows us to interact with objects.
(B) What Is the Difference Between Public and Private Member Functions?
In C++, every class controls who can access its members using access specifiers.
These act like doors or security levels inside the class.
The two most important ones are:
1. Public Members
● Can be accessed from anywhere
● Both inside and outside the class
● Mostly used for functions that allow user interaction with the object
Example:
class A {
public:
void display() {}
};
Here, display() can be called by any object in main().
2. Private Members
● Can be accessed only inside the class
● Cannot be accessed directly using an object
● Ensures security and data protection
Easy2Siksha.com
Example:
class A {
private:
int secret;
};
If you try:
A obj;
obj.secret = 10; // ERROR
The program will not allow it.
➤ Key Differences (Simple Points)
Feature
Public
Private
Accessibility
Anywhere (inside + outside class)
Only inside the class
Security
Low (open to all)
High (restricted)
Use
For functions that need user access
For sensitive data/functions
Access using object
Allowed
Not allowed
Simple Example to Understand
Imagine a bank account:
• Private → balance (you don’t want anyone directly modifying it)
• Public → deposit(), withdraw() (functions that safely modify the balance)
This protects data while still allowing controlled access.
(C) Explain the Need of Inheritance With an Example
Inheritance is one of the most important features of OOP.
➤ What Is Inheritance?
Inheritance allows one class (child class) to acquire the properties and functions of another
class (parent class).
It promotes code reuse, reduces duplication, and helps create a logical structure in
programs.
Easy2Siksha.com
Why Do We Need Inheritance?
Think about real life:
A Car is a vehicle.
A Bike is also a vehicle.
All vehicles have some common properties like:
• speed
• color
• company name
Instead of writing these again and again for every vehicle type, C++ allows us to create a
base class (Vehicle) and let Car, Bike, Truck inherit from it.
Benefits of Inheritance:
1. Reusability of code
→ Write once, use many times
2. Hierarchy (clear structure)
→ Like Parent → Child relationship
3. Easier maintenance
→ Change in base class affects all derived classes
4. Avoids duplication
→ Common properties stored at one place
Simple Example of Inheritance
Base Class:
class Vehicle {
public:
int speed;
void showSpeed() {
cout << "Speed: " << speed;
}
};
Derived Class:
class Car : public Vehicle {
public:
string brand;
};
Easy2Siksha.com
Using the Derived Class:
int main() {
Car c1;
c1.speed = 120; // inherited property
c1.brand = "Toyota";
c1.showSpeed(); // inherited function
}
➤ Explanation of Example (Easy Words)
• We created a Vehicle class that has speed and a function to display speed.
• Then we created a Car class that inherited everything from Vehicle.
• That means Car automatically has speed and showSpeed(), even though we never
wrote those again.
This is the power and usefulness of inheritance.
Just like children inherit qualities from parents, in C++, classes can inherit properties from
other classes.
Conclusion
C++ uses objects to represent real-world entities through classes. Objects are created using
the class blueprint and accessed with the dot operator. Access specifiers like public and
private help control who can use class members, ensuring safety and proper structure.
Inheritance is needed to create expandable, reusable, and efficient program designs by
allowing one class to reuse code from another.
Together, these concepts make C++ a strong object-oriented language that simplifies coding
and promotes better program organization.
8. What is operator overloading? What is the need of overloading an operator? I ist the
operators that can be overloaded and one that cannot be overloaded. Give reasons why
some operators cannot be overloaded.
Ans: When we write programs, we often use operators like +, -, *, and == to perform
operations on basic data types such as integers and floats. But what happens when we
create our own data types, like classes for complex numbers, fractions, or strings? Wouldn’t
it be nice if we could use the same familiar operators on them too?
Easy2Siksha.com
This is where operator overloading comes in. It allows us to redefine how operators work
for user-defined types, making code more natural and readable. Let’s explore what operator
overloading is, why we need it, which operators can be overloaded, and why some cannot.
What is Operator Overloading?
Operator overloading is a feature in C++ that allows programmers to redefine the meaning
of operators for user-defined data types (like classes and structures).
In simple words:
• Normally, + adds two numbers.
• With operator overloading, we can make + add two complex numbers, concatenate
two strings, or even merge two objects.
It’s like teaching the operator new tricks depending on the context.
Example of Operator Overloading
Suppose we have a class for complex numbers:
cpp
class Complex {
int real, imag;
public:
Complex(int r=0, int i=0) : real(r), imag(i) {}
Complex operator + (const Complex& c) {
return Complex(real + c.real, imag + c.imag);
}
};
Now, if we write:
cpp
Complex c1(2, 3), c2(4, 5);
Complex c3 = c1 + c2;
Instead of giving an error, the compiler understands that + means “add the real parts and
add the imaginary parts.”
This makes the code intuitive, almost like working with built-in types.
Why Do We Need Operator Overloading?
1. Readability and Natural Syntax
o Without operator overloading, we might need functions like addComplex(c1,
c2).
Easy2Siksha.com
o With overloading, we simply write c1 + c2.
o The code looks cleaner and easier to understand.
2. Consistency with Built-in Types
o We use + for integers and floats. Why not for complex numbers or matrices?
o Operator overloading makes user-defined types behave like built-in types.
3. Encapsulation and Abstraction
o It hides the internal details of how operations are performed.
o The user just uses the operator without worrying about implementation.
4. Flexibility
o We can define custom behavior for operators depending on the class.
o Example: Overloading == to compare two student objects based on roll
number.
In short: Operator overloading makes programming more intuitive, expressive, and
powerful.
Operators That Can Be Overloaded
Most operators in C++ can be overloaded. Here’s a list:
1. Arithmetic Operators
• +, -, *, /, %
• Example: Adding two matrices, multiplying two fractions.
2. Relational Operators
• ==, !=, <, >, <=, >=
• Example: Comparing two strings or student objects.
3. Logical Operators
• &&, ||, !
• Example: Defining custom truth conditions for objects.
4. Bitwise Operators
• &, |, ^, ~, <<, >>
• Example: Overloading << for output streams (cout).
5. Assignment Operators
• = can be overloaded to copy objects properly.
6. Increment/Decrement Operators
• ++, -- (both prefix and postfix).
Easy2Siksha.com
7. Subscript Operator
• [] can be overloaded to access elements in custom containers.
8. Function Call Operator
• () can be overloaded to make objects callable like functions.
9. Pointer Operators
• ->, * can be overloaded for smart pointers.
Operators That Cannot Be Overloaded
Not all operators can be overloaded. Some are restricted to preserve language integrity.
Operators that cannot be overloaded:
• :: (scope resolution)
• . (member access)
• .* (pointer-to-member access)
• ?: (ternary conditional operator)
• sizeof (size of operator)
• typeid (runtime type information)
Why Some Operators Cannot Be Overloaded?
1. Preserve Language Structure
o Operators like :: and . are fundamental to how C++ identifies scope and
members.
o Allowing overloading would break the basic structure of the language.
2. Avoid Confusion
o If sizeof could be overloaded, it might give misleading results.
o Example: A programmer might redefine sizeof to return something other
than memory size, causing chaos.
3. Maintain Compiler Control
o Some operators are tightly bound to compiler behavior (like ?:).
o Overloading them would interfere with how the compiler generates code.
In short: These restrictions ensure that operator overloading enhances flexibility
without compromising clarity and reliability.
Conclusion
Operator overloading is one of the most powerful features of C++. It allows programmers to
extend the meaning of operators to user-defined types, making code elegant and natural.
However, it comes with boundaries—some operators are too fundamental to be changed.
Easy2Siksha.com
By understanding which operators can be overloaded and why some cannot, we appreciate
the balance C++ maintains between flexibility and stability. Operator overloading is not just
a technical trick—it’s a way to make programming feel closer to human thinking, where
symbols carry meaning across different contexts.
“This paper has been carefully prepared for educaonal purposes. If you noce any
mistakes or have suggesons, feel free to share your feedback.”
